package ex2.LinkedBinaryTree;

import jsjf.BinaryTreeADT;
import jsjf.exceptions.ElementNotFoundException;
import jsjf.exceptions.EmptyCollectionException;
import week4.ArrayUnorderedList;
import week4.UnorderedListADT;
import week6.BinaryTreeNode;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;


public class LinkedBinaryTree<T> implements BinaryTreeADT<T>, Iterable<T>
{
    protected BinaryTreeNode<T> root;
    protected int modCount;
    protected LinkedBinaryTree<T> left,right;

    // 创建一个空的二叉树。
    public LinkedBinaryTree()
    {
        root = null;
    }

    // 创建以指定元素为根的二叉树。
    public LinkedBinaryTree(T element)
    {
        root = new BinaryTreeNode<T>(element);
    }

    // 创建以指定元素为根元素的二叉树，把树作为它的左子树和右子树
    public LinkedBinaryTree(T element, LinkedBinaryTree<T> left,
                            LinkedBinaryTree<T> right)
    {
        root = new BinaryTreeNode<T>(element);
        root.setLeft(left.root);
        root.setRight(right.root);
        this.left = left;
        this.right = right;
    }

    // 返回对根元素的引用
    public T getRootElement() throws EmptyCollectionException
    {
        if (root == null)
        {
            throw new ElementNotFoundException("LinkedBinaryTree");
        }
        else
            return root.element;
    }

    // 返回对根节点的引用
    protected BinaryTreeNode<T> getRootNode() throws EmptyCollectionException
    {
        if (isEmpty()) {
            throw new EmptyCollectionException("BinaryTreeNode ");
        }
        return root;
    }

    // 返回此树根的左子树。
    public LinkedBinaryTree<T> getLeft()
    {
        return left;
    }

    // 返回此树的根的右子树。
    public LinkedBinaryTree<T> getRight()
    {
        return right;
    }

    // 如果此二叉树为空，则返回true，否则返回false。
    public boolean isEmpty()
    {
        return (root == null);
    }

    // 返回此树的整数大小。
    public int size()
    {
        return 1 + root.numChildren();
    }

    // 返回这棵树的高度。
    public int getHeight()
    {
        return height(root);
    }

    // 返回指定节点的高度。
    public int height(BinaryTreeNode<T> node)
    {
        int left;
        int right;
        if (node == null)
        {
            return 0;
        }
        else
        {
            left = height(node.getLeft());
            right = height(node.getRight());
            if (left < right)
                return right + 1;
            else
                return left + 1;
        }
    }

    public void removeRightSubtree(LinkedBinaryTree<T> tree)
    {
        tree.right = null;
    }

    public void removeAllElements()
    {
        root = null;
    }

    public boolean contains(T targetElement)
    {
        return findAgain(targetElement, root) != null;
    }


    public T find(T targetElement) throws ElementNotFoundException
    {
        BinaryTreeNode<T> current = findAgain(targetElement, root);

        if (current == null)
            throw new ElementNotFoundException("LinkedBinaryTree");

        return (current.getElement());
    }


    private BinaryTreeNode<T> findAgain(T targetElement,
                                       BinaryTreeNode<T> next)
    {
        if (next == null)
            return null;

        if (next.getElement().equals(targetElement))
            return next;

        BinaryTreeNode<T> temp = findAgain(targetElement, next.getLeft());

        if (temp == null)
            temp = findAgain(targetElement, next.getRight());

        return temp;
    }

    // 返回这个二叉树的字符串表示形式，以有序的方式显示节点。
    public String toString()
    {
        UnorderedListADT<BinaryTreeNode<T>> nodes =
                new ArrayUnorderedList<BinaryTreeNode<T>>();
        UnorderedListADT<Integer> levelList =
                new ArrayUnorderedList<Integer>();
        BinaryTreeNode<T> current;
        String result = "";
        int printDepth = this.getHeight();
        int possibleNodes = (int)Math.pow(2, printDepth + 1); // 最多的结点数 + 1
        int countNodes = 0;

        nodes.addToRear(root);
        Integer currentLevel = 0;
        Integer previousLevel = -1;
        levelList.addToRear(currentLevel);

        while (countNodes < possibleNodes)
        {
            countNodes = countNodes + 1;
            current = nodes.removeFirst();
            currentLevel = levelList.removeFirst();
            if (currentLevel > previousLevel)
            {
                result = result + "\n\n";
                previousLevel = currentLevel;
                for (int j = 0; j < ((Math.pow(2, (printDepth - currentLevel))) - 1); j++)
                    result = result + " ";
            }
            else
            {
                for (int i = 0; i < ((Math.pow(2, (printDepth - currentLevel + 1)) - 1)) ; i++)
                {
                    result = result + " ";
                }
            }
            if (current != null)
            {
                result = result + (current.getElement()).toString();
                nodes.addToRear(current.getLeft());
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(current.getRight());
                levelList.addToRear(currentLevel + 1);
            }
            else {
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                result = result + " ";
            }

        }

        return result;
    }

    // 使用iteratorInOrder方法
    public Iterator<T> iterator()
    {
        return iteratorInOrder();
    }


    public Iterator<T> iteratorInOrder()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        inOrder(root, tempList);

        return new TreeIterator(tempList.iterator());
    }

    // 执行递归的中序遍历。
    protected void inOrder(BinaryTreeNode<T> node,
                           ArrayUnorderedList<T> tempList)
    {
        if (node != null)
        {
            inOrder(node.getLeft(), tempList);
            tempList.addToRear(node.getElement());
            inOrder(node.getRight(), tempList);
        }
    }

    // 通过调用从根开始的重载递归先序方法，对这个二叉树执行先序遍历。
    public Iterator<T> iteratorPreOrder()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        preOrder(root, tempList);

        return new TreeIterator(tempList.iterator());
    }

    // 执行递归预序遍历。
    protected void preOrder(BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList)
    {
        if (node != null)
        {
            tempList.addToRear(node.getElement());
            preOrder(node.getLeft(), tempList);
            preOrder(node.getRight(), tempList);
        }
    }

    // 通过调用从根开始的重载递归后序方法，对这个二叉树执行后序遍历。
    public Iterator<T> iteratorPostOrder()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        postOrder(root, tempList);

        return new TreeIterator(tempList.iterator());
    }

    // 执行递归后序遍历。
    protected void postOrder(BinaryTreeNode<T> node,
                             ArrayUnorderedList<T> tempList)
    {
        if (node != null)
        {
            postOrder(node.getLeft(), tempList);
            postOrder(node.getRight(), tempList);
            tempList.addToRear(node.getElement());
        }
    }

    // 使用tempList对这棵二叉树执行层序遍历。
    public Iterator<T> iteratorLevelOrder()
    {
        ArrayUnorderedList<BinaryTreeNode<T>> nodes =
                new ArrayUnorderedList<BinaryTreeNode<T>>();
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        BinaryTreeNode<T> current;

        nodes.addToRear(root);

        while (!nodes.isEmpty())
        {
            current = nodes.removeFirst();

            if (current != null)
            {
                tempList.addToRear(current.getElement());
                if (current.getLeft() != null)
                    nodes.addToRear(current.getLeft());
                if (current.getRight() != null)
                    nodes.addToRear(current.getRight());
            }
            else
                tempList.addToRear(null);
        }

        return new TreeIterator(tempList.iterator());
    }

    //层序递归输出
    public void LevelOrderToString(){
        int height = getHeight();
        if(root != null)
            for(int x = 1; x <= height; x++){
            levelOrder(root,x);
        }
    }
    private void levelOrder(BinaryTreeNode root,int level){
        if(root == null || level < 1){
            return;
        }
        if(level == 1){
            System.out.print(root.getElement() + "\n");
            return;
        }
        levelOrder(root.getLeft(),level - 1);
        levelOrder(root.getRight(),level - 1);
    }


    //层序非递归输出
    public void LevelOrderToString2(){
        ArrayUnorderedList<BinaryTreeNode<T>> nodes =
                new ArrayUnorderedList<BinaryTreeNode<T>>();
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        BinaryTreeNode<T> current;

        nodes.addToRear(root);

        while (!nodes.isEmpty())
        {
            current = nodes.removeFirst();
            System.out.print(current.getElement()+"\n");
            if (current != null)
            {
                tempList.addToRear(current.getElement());
                if (current.getLeft() != null)
                    nodes.addToRear(current.getLeft());
                if (current.getRight() != null)
                    nodes.addToRear(current.getRight());
            }
            else
                tempList.addToRear(null);
        }
    }

    // 内部类来表示这个树的元素上的迭代器
    private class TreeIterator implements Iterator<T>
    {
        private int expectedModCount;
        private Iterator<T> iter;

        // 使用指定的迭代器设置此迭代器。
        public TreeIterator(Iterator<T> iter)
        {
            this.iter = iter;
            expectedModCount = modCount;
        }

        // 如果迭代器在迭代中至少有一个元素要交付，则返回true。
        public boolean hasNext() throws ConcurrentModificationException
        {
            if (!(modCount == expectedModCount))
                throw new ConcurrentModificationException();

            return (iter.hasNext());
        }

       // 返回迭代中的下一个元素。如果这个迭代中没有更多的元素，就会抛出NoSuchElementException。
        public T next() throws NoSuchElementException
        {
            if (hasNext())
                return (iter.next());
            else
                throw new NoSuchElementException();
        }

        // 不支持删除操作
        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }
}
